package com.leetcode.questiononehundardandfifty.区间;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author wtcode
 * @Description
 * @date 2025/3/27 - 14:16
 */
public class Answer {

    public static void main(String[] args) {
        int[][] nums = {{1,3},{2,6},{8,10},{15,18}};
        //summaryRanges(nums);
        //merge(nums);
        findMinArrowShots(nums);

    }

    // 汇总区间
    public static List<String> summaryRanges(int[] nums) {
        List<String> arrayList = new ArrayList();

        int len = nums.length;
        int left = 0;
        int right = 0;
        while (left < len){
            right = left +1;
            while(right < len && nums[right] == nums[right-1] + 1){
                right++;
            }
            StringBuilder builder = new StringBuilder(Integer.toString(nums[left]));
            if(left < right-1){
                builder.append("->");
                builder.append(nums[right-1]);
            }

            arrayList.add(builder.toString());
            left = right;
        }

        return arrayList;

    }

    // 合并区间
    public static int[][] merge(int[][] intervals) {
        if(intervals.length == 0){
            return new int[0][2];
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<int[]> res = new ArrayList<int[]>();

        for (int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0];
            int R = intervals[i][1];

            if(res.size() == 0 || res.get(res.size()-1)[1] < L){
                res.add(new int[]{L,R});
            }else {
                R = Math.max(R,res.get(res.size()-1)[1]);
                res.get(res.size()-1)[1] = R;
            }
        }

        return res.toArray(new int[res.size()][]);
    }

    // 插入区间
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length == 0){
            return new int[][]{newInterval};
        }
        List<int[]> arrayList = new ArrayList<int[]>();
        int len = intervals.length;
        int i = 0;
        while (i < len){

            while (i < len && intervals[i][1] < newInterval[0]){
                arrayList.add(intervals[i]);
                i++;
            }

            while (i < len && intervals[i][0] <= newInterval[1]){
                newInterval[0] = Math.min(intervals[i][0],newInterval[0]);
                newInterval[1] = Math.max(intervals[i][1],newInterval[1]);
                i++;
            }
            arrayList.add(newInterval);

            while (i < len && intervals[i][0] > newInterval[0]){
                arrayList.add(intervals[i]);
                i++;
            }

        }

        return arrayList.toArray(new int[arrayList.size()][2]);
    }


    // 用最少数量的箭引爆气球
    public static int findMinArrowShots(int[][] points) {
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });

        int ans = 0;
        long pre = Long.MIN_VALUE;
        for (int[] p : points) {
            if (p[0] > pre) { // 上一个放的点在区间左边
                ans++;
                pre = p[1]; // 在区间的最右边放一个点
            }
        }
        return ans;

    }

}
